package 剑指offer_leetcode;

/**
 * JZ37序列化二叉树
 */
public class 剑指Offer37_序列化二叉树 {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null)
            return "#";
        StringBuilder sb = new StringBuilder();
        serializeFunction(root,sb);
        return sb.toString();
    }

    void serializeFunction(TreeNode root,StringBuilder sb){
        if(root==null){
            sb.append("#");
            return;
        }
        sb.append(root.val).append("!");
        serializeFunction(root.left,sb);
        serializeFunction(root.right,sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data=="#"||data==null||data.length()==0)
            return null;
        return deserializeFunction(data);
    }

    int index = 0;
    TreeNode deserializeFunction(String str){
        if(str.charAt(index)=='#'){
            index++;
            return null;
        }
        int val = 0;
        int sign = 1;
        while(index!=str.length()&&str.charAt(index)!='!'){
            if(str.charAt(index)=='-'){
                sign = -1 * sign;
            }else if(str.charAt(index)=='+'){
                sign = 1 * sign;
            }else{
                val = val * 10 + (str.charAt(index) - '0');
            }
            index++;
        }
        val = sign * val;
        TreeNode root = new TreeNode(val);
        if(index==str.length())
            return root;
        else
            index++;
        root.left = deserializeFunction(str);
        root.right = deserializeFunction(str);
        return root;
    }
}
